using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Diagnostics;

namespace TSP
{
	public class ProblemAndSolver
	{
		public class TSPSolution
		{
			/// <summary>
			/// we use the representation [cityB,cityA,cityC] 
			/// to mean that cityB is the first city in the solution, cityA is the second, cityC is the third 
			/// and the edge from cityC to cityB is the final edge in the path.  
			/// you are, of course, free to use a different representation if it would be more convenient or efficient 
			/// for your node data structure and search algorithm. 
			/// </summary>
			public ArrayList
				Route;

			public TSPSolution(ArrayList iroute)
			{
				Route = new ArrayList(iroute);
			}

			/// <summary>
			///  compute the cost of the current route.  does not check that the route is complete, btw.
			/// assumes that the route passes from the last city back to the first city. 
			/// </summary>
			/// <returns></returns>
			public double costOfRoute()
			{
				// go through each edge in the route and add up the cost. 
				int x;
				City here;
				double cost = 0D;

				for (x = 0; x < Route.Count - 1; x++)
				{
					here = Route[x] as City;
					cost += here.costToGetTo(Route[x + 1] as City);
				}
				// go from the last city to the first. 
				here = Route[Route.Count - 1] as City;
				cost += here.costToGetTo(Route[0] as City);
				return cost;
			}
		}

		#region private members
		private const int DEFAULT_SIZE = 25;

		private const int CITY_ICON_SIZE = 5;

		/// <summary>
		/// the cities in the current problem.
		/// </summary>
		private City[] Cities;
		/// <summary>
		/// a route through the current problem, useful as a temporary variable. 
		/// </summary>
		private ArrayList Route;
		/// <summary>
		/// best solution so far. 
		/// </summary>
		private TSPSolution bssf;

		/// <summary>
		/// how to color various things. 
		/// </summary>
		private Brush cityBrushStartStyle;
		private Brush cityBrushStyle;
		private Pen routePenStyle;


		/// <summary>
		/// keep track of the seed value so that the same sequence of problems can be 
		/// regenerated next time the generator is run. 
		/// </summary>
		private int _seed;
		/// <summary>
		/// number of cities to include in a problem. 
		/// </summary>
		private int _size;

		/// <summary>
		/// random number generator. 
		/// </summary>
		private Random rnd;
		#endregion

		#region public members.
		public int Size
		{
			get { return _size; }
		}

		public int Seed
		{
			get { return _seed; }
		}
		#endregion

		public const int DEFAULT_SEED = -1;

		#region Constructors
		public ProblemAndSolver()
		{
			initialize(DEFAULT_SEED, DEFAULT_SIZE);
		}

		public ProblemAndSolver(int seed)
		{
			initialize(seed, DEFAULT_SIZE);
		}

		public ProblemAndSolver(int seed, int size)
		{
			initialize(seed, size);
		}
		#endregion

		#region Private Methods

		/// <summary>
		/// reset the problem instance. 
		/// </summary>
		private void resetData()
		{
			Cities = new City[_size];
			Route = new ArrayList(_size);
			bssf = null;

			for (int i = 0; i < _size; i++)
				Cities[i] = new City(rnd.NextDouble(), rnd.NextDouble());

			cityBrushStyle = new SolidBrush(Color.Black);
			cityBrushStartStyle = new SolidBrush(Color.Red);
			routePenStyle = new Pen(Color.LightGray, 1);
			routePenStyle.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;
		}

		private void initialize(int seed, int size)
		{
			this._seed = seed;
			this._size = size;
			if (seed != DEFAULT_SEED)
				this.rnd = new Random(seed);
			else
				this.rnd = new Random();
			this.resetData();
		}

		#endregion

		#region Public Methods

		/// <summary>
		/// make a new problem with the given size.
		/// </summary>
		/// <param name="size">number of cities</param>
		public void GenerateProblem(int size)
		{
			this._size = size;
			resetData();
		}

		/// <summary>
		/// return a copy of the cities in this problem. 
		/// </summary>
		/// <returns>array of cities</returns>
		public City[] GetCities()
		{
			City[] retCities = new City[Cities.Length];
			Array.Copy(Cities, retCities, Cities.Length);
			return retCities;
		}

		/// <summary>
		/// draw the cities in the problem.  if the bssf member is defined, then
		/// draw that too. 
		/// </summary>
		/// <param name="g">where to draw the stuff</param>
		public void Draw(Graphics g)
		{
			float width = g.VisibleClipBounds.Width - 45F;
			float height = g.VisibleClipBounds.Height - 15F;
			Font labelFont = new Font("Arial", 10);

			g.DrawString("n(c) means this node is the nth node in the current solution and incurs cost c to travel to the next node.", labelFont, cityBrushStartStyle, new PointF(0F, 0F));

			// Draw lines
			if (bssf != null)
			{
				// make a list of points. 
				Point[] ps = new Point[bssf.Route.Count];
				int index = 0;
				foreach (City c in bssf.Route)
				{
					if (index < bssf.Route.Count - 1)
						g.DrawString(" " + index + "(" + c.costToGetTo(bssf.Route[index + 1] as City) + ")", labelFont, cityBrushStartStyle, new PointF((float)c.X * width + 3F, (float)c.Y * height));
					else
						g.DrawString(" " + index + "(" + c.costToGetTo(bssf.Route[0] as City) + ")", labelFont, cityBrushStartStyle, new PointF((float)c.X * width + 3F, (float)c.Y * height));
					ps[index++] = new Point((int)(c.X * width) + CITY_ICON_SIZE / 2, (int)(c.Y * height) + CITY_ICON_SIZE / 2);
				}

				if (ps.Length > 0)
				{
					g.DrawLines(routePenStyle, ps);
					g.FillEllipse(cityBrushStartStyle, (float)Cities[0].X * width - 1, (float)Cities[0].Y * height - 1, CITY_ICON_SIZE + 2, CITY_ICON_SIZE + 2);
				}

				// draw the last line. 
				g.DrawLine(routePenStyle, ps[0], ps[ps.Length - 1]);
			}

			// Draw city dots
			foreach (City c in Cities)
			{
				g.FillEllipse(cityBrushStyle, (float)c.X * width, (float)c.Y * height, CITY_ICON_SIZE, CITY_ICON_SIZE);
			}

		}

		/// <summary>
		///  return the cost of the best solution so far. 
		/// </summary>
		/// <returns></returns>
		public double costOfBssf()
		{
			if (bssf != null)
				return (bssf.costOfRoute());
			else
				return -1D;
		}

		private List<TSPSolution> ComputeLowestBound()
		{
			double first = 0;
			List<TSPSolution> lowestBound = new List<TSPSolution>();
			ArrayList distance;
			TSPSolution sol = null;
			for (int i = 0; i < Cities.Length; i++)
			{
				for (int j = 0; j < Cities.Length; j++)
				{
					if (i != j)
					{
						distance = new ArrayList();
						distance.Add(Cities[i]);
						distance.Add(Cities[j]);
						TSPSolution temp = new TSPSolution(distance);
						if (sol == null || temp.costOfRoute() < sol.costOfRoute())
						{
							sol = temp;
						}
					}

				}

				// sol is now the edge leaving i with the smallest cost
				lowestBound.Add(sol);

			}
			return lowestBound;
		}



		/// <summary>
		///  solve the problem.  This is the entry point for the solver when the run button is clicked
		/// right now it just picks a simple solution. 
		/// </summary>
		public void solveProblem()
		{
			int x;
			Route = new ArrayList();
			// this is the trivial solution. 
			for (x = 0; x < Cities.Length; x++)
			{
				Route.Add(Cities[Cities.Length - x - 1]);
			}
			// call this the best solution so far.  bssf is the route that will be drawn by the Draw method. 
			bssf = new TSPSolution(Route);
			// update the cost of the tour. 

			PriorityQueue<State> pq;

			List<TSPSolution> lowestBound = ComputeLowestBound();

			ArrayList distance;
			State state = new State(lowestBound, 0);
			pq = new PriorityQueue<State>(new StateComparer());
			pq.Add(state);

			Stopwatch timer = new Stopwatch();
			timer.Start();
			double bssfCost;
			while (!pq.isEmpty() && timer.Elapsed.TotalSeconds < 60 && (bssfCost = bssf.costOfRoute()) != state.GetCost())
			{
				State currentState = pq.Dequeue();

				if (currentState.GetCost() >= bssfCost) continue;



			}
			//for (int i = 0; i < Cities.Length; i++)
			//{

			//    for (int j = 0; j < Cities.Length; j++)
			//    {
			//        if (i != j)
			//        {
			//            distance = new ArrayList();
			//            distance.Add(Cities[i]);
			//            distance.Add(Cities[j]);
			//            TSPSolution currentSolution = new TSPSolution(distance);
			//            //state = new State(currentSolution.costOfRoute() + lowestBound, 1);
			//        }
			//    }
			//}


			Program.MainForm.tbCostOfTour.Text = " " + bssf.costOfRoute();
			// do a refresh. 
			Program.MainForm.Invalidate();
		}



		public void myBranchAndBound()
		{
			System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
			TSPSolution finalbssf = null;
			double bssfnum = -1;
			double costofrt = 0;

			for (int i = 0; i < 5; i++)
			{
				bssf = new TSPSolution(randomPath());
				costofrt = bssf.costOfRoute();
				if (bssfnum == -1 || costofrt < bssfnum) { bssfnum = costofrt; finalbssf = bssf; }

			}

			bssf = finalbssf;

			PriorityQueue<CostMatrix> q = new PriorityQueue<CostMatrix>(new MatrixComp());
			CostMatrix init = new CostMatrix(ref Cities);
			q.Enqueue(init);

			timer.Start();

			int max = 0;

			while (!q.isEmpty() && timer.Elapsed.TotalSeconds < 60)
			{
				CostMatrix subp = q.Dequeue();

				if (q.Count > max) max = q.Count;

				//if the cost of subproblem is worse than bssf
				if (subp.costSoFar >= costOfBssf()) continue;

				CostMatrix include = null;
				CostMatrix exclude = null;
				MatrixPairs incexc = subp.getIncExc();

				if (incexc == null) continue;

				include = incexc.include;
				exclude = incexc.exclude;

				if (include.comp && include.costSoFar < costOfBssf()) bssf = new TSPSolution(include.GetRoute(ref Cities));
				else betterCost(ref include, ref q);
				betterCost(ref exclude, ref q);
			}

			timer.Stop();

			Program.MainForm.tbCostOfTour.Text = " " + bssf.costOfRoute();
			Program.MainForm.tbElapsedTime.Text = timer.Elapsed.ToString();

			Program.MainForm.Invalidate();
		}

		private bool betterCost(ref CostMatrix cost, ref PriorityQueue<CostMatrix> q)
		{
			if (cost.costSoFar < costOfBssf())
			{
				q.Enqueue(cost);
				return true;
			}
			return false;
		}

		public ArrayList randomPath()
		{
			ArrayList tempCities = new ArrayList(Cities);
			ArrayList randPath = new ArrayList();
			Random random = new Random();
			int rand = 0;
			while (tempCities.Count != 0)
			{
				rand = random.Next(0, tempCities.Count);
				randPath.Add((TSP.City)tempCities[rand]);
				tempCities.RemoveAt(rand);
			}
			return randPath;
		}

		#endregion
	}
}